Dynamic Structural Clustering on Graphs

Abstract

\em Structural Clustering ($\strclu$) is one of the most popular graph clustering paradigms. In this paper, we consider $\strclu$ under Jaccard similarity on a dynamic graph, G = (V, E), subject to edge insertions and deletions (updates). The goal is to maintain certain information under updates, so that the strclu clustering result on∼G can be retrieved in O(|V| + |E|)$ time, upon request. The state-of-the-art worst-case cost is∼O(|V|) per update; we improve this update-time bound \em significantly with the ρ-approximate notion. Specifically, for a specified failure probability, δ^∗, and \em every sequence of∼M updates (no need to know M's value in advance), our algorith..